There has conventionally been considered a path selection problem in a network as a search for a shortest path connecting two points. Representative types of the network include a traffic network regarding traffic of cars and the like, and an information network regarding information communication.
The most famous method for shortest path search is the Dijkstra method. The Dijkstra method is an algorithm that is substantially optimum in terms of a computational theory, but in a case of application to a real problem, has a problem in that, when a shortest path connecting distant points is to be determined, the problem cannot be solved in realistic time because many parts of map information (map data) need to be accessed, for example. An image of the algorithm of the Dijkstra method is to gradually determine a shortest path from a start node (starting point) to a neighboring node, and when arriving at a target node (destination) and there is no probability that another path is the shortest path, end the computation.
In order to solve this problem, some approaches have been taken.
As a most simple method of decreasing the computation time, there is a method of performing the Dijkstra method from both a start point and an end point to narrow down a search range. There is also a method called the A* algorithm for preferentially searching a direction with a smaller straight-line distance to the destination. Those methods are reduced in computation time as compared to the Dijkstra method, but still have a problem in that an enormous amount of time is needed for large-scale data.
Another method is a heuristic method of assuming that when moving between distant areas, a kind of predetermined route is taken, to thereby omit the intermediate search. As a subspecies, there is also a method of forming roads into a hierarchy of a network including roads used for traveling a long distance, such as expressways and highways, and a network including the other roads, and after first determining the shortest path from each of the current position and the destination to the nearest highway, solving the shortest path problem on the highway. Those can be considered as approaches that give up on optimization.
In recent years, there have been adopted approaches in which, for example, a certain kind of preprocessing is performed on the map information (map data) so as to find a solution in a short time when the shortest path is determined later. The most famous of those approaches are the bit vector method and the highway hierarchy method.
In the bit vector method, the map is divided into several areas, and for a set of each node and an area, from among links connecting to the node, a used link for use by the shortest path from the vertex to the node in the area is selected in advance. In searching for the shortest path, the searching is omitted by searching only the used link in a direction from a desired node to an area including the destination. The problems are that the preprocessing takes time and that an increase in memory is caused by storing the used link and the like.
In the highway hierarchy method, links for long distance are determined in advance so that a link for long distance is reached in k links from a start node, and after getting off the link for long distance, the target node is reached in k links. In other words, the link for long distance satisfying the above-mentioned conditions are determined in advance in the approach. The approach is advantageous in that the preprocessing ends when the shortest path is determined only for nodes that are within 2k+1 links from each node, and hence the preprocessing time is shorter than the other approaches. The problem is that there is no guarantee that the network contains the link for long distance.
The technologies of shortest path search have been outlined above, and have been working with some success in a network in which nodes and links are stable to some extent as in the traffic network. However, in the case of the information network in which the relationship between nodes and links changes dynamically, it is difficult to adapt the above-mentioned algorithms in a simple manner. For example, in the case of the information network, the preprocessing and the like cannot be performed realistically. This is because the preprocessing requires a somewhat stable network (that changes little with time) as a precondition.
As a shortest path search for the information network, the following approach has been conventionally used.
The shortest path search generally used in a large scale information network is a path control protocol called Open Shortest Path First (OSPF). This protocol uses the Dijkstra algorithm. This OSPF has a feature in that, while the routers exchange copies of the entire path tables of their own in the conventional distance-vector path control protocol, the routers exchange only the link states and each router computes the shortest path. Therefore, the OSPF has an advantage that the amount of data to be exchanged between the routers is significantly small as compared to the conventional distance-vector algorithm and hence the amount of data exchange can be made smaller irrespective of the scale of the network system.
In actual operation, the OSPF performs the path selection by dividing an autonomous system (AS), which is a set of operating routers, into a plurality of areas so that all routers belonging to one area are configured to have the same link state database and each of the routers computes the shortest path from the router to all the destination based on the link state database.
However, the OSPF performs the shortest path computation with the little computational resource of the router, and hence has had problems in that the restriction in computational resource limits the area and does not allow the shortest path computation to be performed frequently. In the case of the information network, the network status changes dynamically as compared to the traffic network, and hence while the shortest path computation essentially needs to be performed in real time if possible, such ideal situation is hard to achieve.
In addition, irrespective of whether the relationship between the nodes and the links is stable in time, the shortest path computations are common in determining the shortest path by computing and comparing the lengths of the paths.
Literatures describing the technologies relating to this invention include Japanese Patent Application Laid-open Nos. 2009-141425 and 2010-041429 (hereinafter referred to as Patent Literatures 1 and 2, respectively). The technologies disclosed in those patent literatures are both technologies involving transmitting a search packet to the real network and selecting the path based on the state of the packet. According to such methods, in order to grasp the network state of the entire path, there is a need to actually transmit to the network the number of packets corresponding to the scale of the network and then observe the state. Therefore, it is considered that applying such technologies to a large-scale network to select a path is difficult.